package com.lims.algorithm.algset.graph.basic;


import java.io.IOException;
import java.util.Scanner;

/**
 * <功能简述>
 *
 * @author lims
 * @date 2020-08-19 14:41
 */
public class ListUDG extends GraphListAbs {

    /*protected class EdgeNode {
     *//**
     * 边所指向的顶点的位置
     *//*
        protected int iVex;
        *//**
     * 指向下一条弧的指针
     *//*
        protected EdgeNode nextEdge;
    }

    protected class VertexNode {
        *//**
     * 顶点数据信息
     *//*
        char data;
        *//**
     * 指向第一条依附该顶点的弧
     *//*
        protected EdgeNode firstEdge;
    }

    *//**
     * 顶点数组
     *//*
    private VertexNode[] vertes;*/

    /**
     * 创建图(自己输入数据)
     */
    public ListUDG() {
        // 输入"顶点数"和"边数"
        System.out.printf("input vertex number: ");
        int vlen = readInt();
        System.out.printf("input edge number: ");
        int elen = readInt();
        if (vlen < 1 || elen < 1 || (elen > (vlen * (vlen - 1)))) {
            System.out.printf("input error: invalid parameters!\n");
            return;
        }

        // 初始化"顶点"
        vertes = new VertexNode[vlen];
        for (int i = 0; i < vertes.length; i++) {
            System.out.printf("vertex(%d): ", i);
            vertes[i] = new VertexNode();
            vertes[i].setData(readChar());
            vertes[i].setFirstEdge(null);
        }

        // 初始化"边"
        for (int i = 0; i < elen; i++) {
            // 读取边的起始顶点和结束顶点
            System.out.printf("edge(%d):", i);
            char c1 = readChar();
            char c2 = readChar();
            int p1 = getPosition(c1);
            int p2 = getPosition(c2);
            // 初始化node1
            EdgeNode node1 = new EdgeNode();
            node1.setiVex(p2);
            // 将node1链接到"p1所在链表的末尾"
            if (vertes[p1].getFirstEdge() == null) {
                vertes[p1].setFirstEdge(node1);
            } else {
                linkLast(vertes[p1].getFirstEdge(), node1);
            }
            // 初始化node2
            EdgeNode node2 = new EdgeNode();
            node2.setiVex(p1);
            // 将node2链接到"p2所在链表的末尾"
            if (vertes[p2].getFirstEdge() == null) {
                vertes[p2].setFirstEdge(node2);
            } else {
                linkLast(vertes[p2].getFirstEdge(), node2);
            }
        }
    }

    /**
     * 创建图(用已提供的矩阵)
     *
     * @param vexs  顶点数组
     * @param edges 边数组
     */
    public ListUDG(char[] vexs, char[][] edges) {
        // 初始化"顶点数"和"边数"
        int vlen = vexs.length;
        int elen = edges.length;

        // 初始化"顶点"
        vertes = new VertexNode[vlen];
        for (int i = 0; i < vertes.length; i++) {
            vertes[i] = new VertexNode();
            vertes[i].setData(vexs[i]);
            vertes[i].setFirstEdge(null);
        }

        // 初始化"边"
        for (int i = 0; i < elen; i++) {
            // 读取边的起始顶点和结束顶点
            char c1 = edges[i][0];
            char c2 = edges[i][1];
            // 读取边的起始顶点和结束顶点
            int p1 = getPosition(edges[i][0]);
            int p2 = getPosition(edges[i][1]);

            // 初始化node1
            EdgeNode node1 = new EdgeNode();
            node1.setiVex(p2);
            // 将node1链接到"p1所在链表的末尾"
            if (vertes[p1].getFirstEdge() == null) {
                vertes[p1].setFirstEdge(node1);
            } else {
                linkLast(vertes[p1].getFirstEdge(), node1);
            }

            // 初始化node2
            EdgeNode node2 = new EdgeNode();
            node2.setiVex(p1);
            // 将node2链接到"p2所在链表的末尾"
            if (vertes[p2].getFirstEdge() == null) {
                vertes[p2].setFirstEdge(node2);
            } else {
                linkLast(vertes[p2].getFirstEdge(), node2);
            }

        }
    }

    /**
     * 将node节点链接到list的最后
     */
    private void linkLast(EdgeNode list, EdgeNode node) {
        EdgeNode p = list;

        while (p.getNextEdge() != null) {
            p = p.getNextEdge();
        }
        p.setNextEdge(node);
    }

    /**
     * 返回ch位置
     */
    private int getPosition(char ch) {
        for (int i = 0; i < vertes.length; i++) {
            if (vertes[i].getData() == ch) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 读取一个输入字符
     */
    @Override
    protected char readChar() {
        char ch = '0';

        do {
            try {
                ch = (char) System.in.read();
            } catch (IOException e) {
                e.printStackTrace();
            }
        } while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));

        return ch;
    }

    /**
     * 读取一个输入字符
     */
    @Override
    protected int readInt() {
        Scanner scanner = new Scanner(System.in);
        return scanner.nextInt();
    }

    /**
     * 打印矩阵队列图
     */
    @Override
    public void print() {
        System.out.printf("List GraphUDG:\n");
        for (int i = 0; i < vertes.length; i++) {
            System.out.printf("%d(%c): ", i, vertes[i].getData());
            EdgeNode node = vertes[i].getFirstEdge();
            while (node != null) {
                System.out.printf("%d(%c) ", node.getiVex(), vertes[node.getiVex()].getData());
                node = node.getNextEdge();
            }
            System.out.printf("\n");
        }
    }

    /****************************************************/
    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        char[][] edges = new char[][]{
                {'A', 'C'},
                {'A', 'D'},
                {'A', 'F'},
                {'B', 'C'},
                {'C', 'D'},
                {'E', 'G'},
                {'F', 'G'}};
        ListUDG pG;

        // 自定义"图"(输入矩阵队列)
        //pG = new ListUDG();
        // 采用已有的"图"
        pG = new ListUDG(vexs, edges);

        pG.print();   // 打印图
    }
}
